package 第2节数组;
//插值查找
public class InterpolationSearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        int key = 8;
        int low = 0;
        int high = arr.length - 1;
        int mid = -1;
        while (true) {
            mid = low + (int)(1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
            if (mid > high || mid < low) {
                mid = -1;
                break;
            }
            if (arr[mid] < key) {
                low = mid + 1;
            } else if (key < arr[mid]){
                high = mid - 1;
            } else {
                break;
            }
            if (high < low) {
                mid = -1;
                break;
            }
        }
        System.out.println(mid);
    }
}
